package com.wc.alorithm_luogu.P1990;

import java.util.Scanner;

/**
 * @Author congege
 * @Description 难度很高
 * 覆盖墙壁
 * https://www.luogu.com.cn/problem/P1990
 * @Date Created in 2023/9/14-9:38
 */
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        scan.close();
        /**
         * f(n) 表示在2 * n的瓷砖上铺满要多少种
         * g(n) 表示在2 * n的瓷砖上面铺少一个格子有多少种
         */
        int[] f = new int[N + 10];
        int[] g = new int[N + 10];

        f[1] = 1;
        f[2] = 2;

        g[1] = 0;
        g[2] = 2;

        int mod = 10000;
        for (int i = 3; i <= N; i++) {
            f[i] = (f[i - 1] + f[i - 2] + g[i - 1])% mod;
            g[i] = (g[i - 1] + 2 * f[i - 2]) % mod;
        }
        System.out.println(f[N]);
    }
}
